Search results for "Finite state"

Simple method for limiting delay of optimized interleavers for turbo-codes

2000

An iterative interleaver growth algorithm is extended to allow the delay and required memory of designed interleavers to be halved with negligible performance loss. The original algorithm is efficient for two-component parallel concatenated turbo-codes with given constituent encoders that are optimum with regard to a cost function satisfying some mild conditions. However, it is only actually optimum if the selected set of patterns is representative of low-weight turbo-codewords. The new interleaver uses all terminating error patterns having an input weight not greater than a fixed IWX and single-coder output weight not greater than WX is proposed.

On extremal cases of Hopcroft’s algorithm

2010

AbstractIn this paper we consider the problem of minimization of deterministic finite automata (DFA) with reference to Hopcroft’s algorithm. Hopcroft’s algorithm has several degrees of freedom, so there can exist different executions that can lead to different sequences of refinements of the set of the states up to the final partition. We find an infinite family of binary automata for which such a process is unique, whatever strategy is chosen. Some recent papers (cf. Berstel and Carton (2004) [3], Castiglione et al. (2008) [6] and Berstel et al. (2009) [1]) have been devoted to find families of automata for which Hopcroft’s algorithm has its worst execution time. They are unary automata as…

On Extremal Cases of the Hopcroft's Algorithm

2010

In this paper we consider the problem of minimization of deterministic finite automata (DFA) with reference to Hopcroft’s algorithm. Hopcroft’s algorithm has several degrees of freedom, so there can exist different executions that can lead to different sequences of refinements of the set of the states up to the final partition. We find an infinite family of binary automata for which such a process is unique, whatever strategy is chosen. Some recent papers (cf. Berstel and Carton (2004) [3], Castiglione et al. (2008) [6] and Berstel et al. (2009) [1]) have been devoted to find families of automata for which Hopcroft’s algorithm has its worst execution time. They are unary automata associated…

Stochastical Real Time Finite State Machine LPC for Planar Manipulator Control System Model estimation

2005

This paper presents a new stochastical real-time LPC (Last Principal Component) algorithm to estimate single-input-single-output (SISO) and multiple-input-multiple-output (MIMO) varying time models from input output data clusters of non stationary black boxes. Each of data clusters is on a time window. An application to estimate the control system model of a planar manipulator is developed. In fact many mathematical models of physical systems are non stationary such as industrial manipulator model. A real time estimation algorithm via stochastical LPC algorithm and an appraiser called "finite state machine" is then described For every data cluster the finite state machine updates the parame…

On-line construction of a small automaton for a finite set of words

2009

In this paper we describe a ``light'' algorithm for the on-line construction of a small automaton recognising a finite set of words. The algorithm runs in linear time. We carried out good experimental results on the suffixes of a text, showing how this automaton is small. For the suffixes of a text, we propose a modified construction that leads to an even smaller automaton.

Size of Quantum Finite State Transducers

2007

Sizes of quantum and deterministic finite state transducers are compared in the case when both quantum and deterministic finite state transducers exist. The difference in size may be exponential.

Verification of Well-Formed Communicating Recursive State Machines

2008

AbstractIn this paper we introduce a new (non-Turing equivalent) formal model of recursive concurrent programs called well-formed communicating recursive state machines (CRSM). CRSM extend recursive state machines (RSM) by allowing a restricted form of concurrency: a state of a module can be refined into a finite collection of modules (working in parallel) in a potentially recursive manner. Communication is only possible between the activations of modules invoked on the same fork. We study the model-checking problem of CRSM with respect to specifications expressed in a temporal logic that extends CaRet with a parallel operator (ConCaRet). We propose a decision algorithm that runs in time ex…

Power dispatching techniques as a finite state machine for a standalone photovoltaic system with a hybrid energy storage

2020

Standalone photovoltaic system (SPVS) is usually embedded with an energy storage unit to overcome the intermittency of photovoltaic (PV) generation as well as to address load variations in off-grid operation. In SPVS energy systems, batteries can serve as the long term energy storage and contributing to the large portion of the energy demand but to overcome the load intermittency, it necessitates a fast response energy storage embedded with the battery as a hybrid energy storage (HES) for dynamic loads (e.g., Electric Vehicle loads, emergency power management). In this work, Lead-Acid (LA) battery and supper capacitor (SC) array are used as the HES. HES helps not only in increasing more uti…

Method of changing the operation of wireless network nodes

2013

Circular sturmian words and Hopcroft’s algorithm

2009

AbstractIn order to analyze some extremal cases of Hopcroft’s algorithm, we investigate the relationships between the combinatorial properties of a circular sturmian word (x) and the run of the algorithm on the cyclic automaton Ax associated to (x). The combinatorial properties of words taken into account make use of sturmian morphisms and give rise to the notion of reduction tree of a circular sturmian word. We prove that the shape of this tree uniquely characterizes the word itself. The properties of the run of Hopcroft’s algorithm are expressed in terms of the derivation tree of the automaton, which is a tree that represents the refinement process that, in the execution of Hopcroft’s alg…